This invention relates to controlling task execution.
Computational tasks within computational systems often have dependencies that lead to constraints that some tasks start or finish execution before or after other tasks. A partial ordering of the tasks may be imposed to satisfy such constraints. The tasks may be performed by processes running within the same or different runtime environments with some tasks potentially running concurrently. A control process can be implemented to initiate and monitor execution of the tasks, according to a specification of the task dependency constraints.
FIG. 1A shows an example of a graph representing dependencies among tasks, a “dependency graph.” The nodes represent the tasks and the directed links represent dependency constraints. In this example the dependencies among the tasks come from access to a common data structure, in this case a table. An initialize table task 102 sets the size of the table and enters default values within the table. A load table task 104 writes a set of data records into rows of the table. A first link 106 specifies that the initialize table task 102 must execute before the load table task 104. An unload table task 108 reads the data records from the rows of the table to be used in subsequent computation. A second link 110 specifies that the load table task 104 must execute before the unload table task 108. The directionality of a link indicates the order of execution. There is also an implied dependency in that the initialize table task 102 must execute before the unload table task 108.
If tasks to be performed in a computational system are changed (e.g., by adding or deleting tasks) the corresponding dependency graph may need to be changed. Referring to FIG. 1B, the dependency graph 100 is modified, in graph 112, to include a sort table task 114 between the load table task 104 and the unload table task 108. The link 110 between the load table task 104 and the unload table task 108 is replaced by a link 116 between the load table task 104 and the sort table task 114, and a link 118 between the sort table task 114 and the unload table task 108.
Dependency graphs can specify constraints that allow tasks to be performed concurrently. Any one of a group of tasks may be able to execute after a preceding task. More generally, rules can be formulated to determine a partial ordering among tasks with dependencies represented by an acyclic directed graph. An example of a rule for a partial ordering among tasks in a dependency graph is (rule 1): if a directed path through the graph exists from a “predecessor task” to a “successor task” then the successor task must not begin execution until after the predecessor task finishes execution.
FIG. 1C shows a dependency graph 120 where a first group 122 of three tasks that load different parts of a table must all finish execution before any of a second group 124 of three tasks that perform operations (e.g., read, sort, etc.) on parts of the table begins execution. This example illustrates the potential complexity that can exist in some dependency graphs. In a graph with this type of structure the number of links between the groups (9 in this example) increases as the product of the number of tasks in the first group (3 in this example) times the number of tasks in the second group (3 in this example). There are also links to each of the tasks in the first group 122 from an initialize table task 126, and from each of the tasks in the second group 124 to an unload table task 128.